package ink.lovejinhu.leetcode;

import org.junit.Test;

/**
 * @author jinhu
 * created 2021-04-30 9:05
 */
public class Solution_0035 {
    @Test
    public void test() {
        int[] nums = {1, 3, 5, 6};
        int target = 5;
        int i = this.searchInsert(nums, target);
        System.out.println(i);
    }

    /**
     * 数组有序
     * 存在就返回目标数在数组中的索引，不存在返回插入的位置
     *
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) {
            return 0;
        }
        if (target > nums[nums.length - 1]) {
            return nums.length;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
            if (nums[i] < target && nums[i + 1] > target) {
                return i + 1;
            }


        }

        return 0;
    }

    /**
     * 如何二分
     *
     * @param num
     * @param left
     * @param right
     * @param tartget
     * @return
     */
    public int partition(int[] num, int left, int right, int tartget) {
        if (num[(left + right) / 2] == tartget) {
            return left + right / 2;
        }
        int index = this.partition(num, left, (left + right) / 2 - 1, tartget);
        int index01 = this.partition(num, (left + right) / 2 + 1, right, tartget);

        return index;
    }
}
